package _binary_search;

/**
 * 1870. 准时到达的列车最小时速
 */
public class No1870 {
    public int minSpeedOnTime(int[] dist, double hour) {
        int n = dist.length;
        if (n - 1 >= hour) return -1;

        int ans = Integer.MAX_VALUE;

        int left = 1, right = (int) Math.pow(10, 7);
        while (left <= right) {
            int mid = left + (right - left >> 1);
            double curSum = 0;
            for (int i = 0; i < n - 1; i++) {
                curSum += (int) Math.ceil((double) dist[i] / mid);
            }
            curSum += (double) dist[n - 1] / mid;
            if (curSum > hour) left = mid + 1;
            else {
                right = mid - 1;
                ans = Math.min(mid, ans);
            }
        }
        return ans;
    }
}
